xem
lát cắt đỉnh.
Tập láng giềng, còn gọi là
tập láng giềng (mở) của một đỉnh v, ký hiệu NG(v), bao gồm tất cả các đỉnh kề với v không kể v. Nếu kể cả v, tập này được gọi là
tập láng giềng đóng, ký hiệu NG[v]. Nếu không nói rõ, một tập láng giềng được coi là mở. Chỉ số dưới G thường được bỏ qua nếu không gây nhầm lẫn. Trong đồ thị ví dụ, đỉnh 1 có hai hàng xóm: các đỉnh 2 và 5. Đối với đồ thị đơn, số láng giềng của một đỉnh trùng với bậc của đỉnh đó.
- Tập thống trị (dominating set)
Một tập thống trị của một đồ thị là một tập con của tập đỉnh, trong đó hợp của các tập láng giềng đóng của các đỉnh trong tập con đó bao gồm tất cả các đỉnh của đồ thị.
Xem
Độc lập.
- Tập ổn định trong cùng nghĩa với tập độc lập.
- Tập ổn định ngoài cùng nghĩa với tập thống trị.
- Thành phần liên thông
Quan hệ liên thông trong đồ thị vô hướng là quan hệ tương đương, quan hệ này chia tập các đỉnh của đồ thị thành các lớp tương đương, mỗi lớp được gọi là một thành phần liên thông của một đồ thị.
- Thành phần liên thông mạnh
Thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con, trong đó từ mỗi đỉnh của nó đều có đường đi đến mọi đỉnh khác.
Đỉnh v
thống trị đỉnh u nếu có một cạnh từ v tới u. Một tập đỉnh V
thống trị một tập đỉnh
U khác nếu mọi đỉnh trong U đều thuộc V hoặc kề với một đỉnh nào đó trong V. Kích thước của tập thống trị nhỏ nhất được gọi là
chỉ số thống trị γ(G).Tập đỉnh S được gọi là
thống trị ngoài (out-dominating) nếu mọi đỉnh ngoài S đều bị thống trị bởi một đỉnh nào đó thuộc S; gọi là
thống trị trong (in-dominating) nếu mọi đỉnh thuộc S đều bị thống trị bởi một đỉnh nào đó không thuộc S.
là các giá trị thường được gán cho các cạnh của đồ thị. Trọng số thường là các
số thực. Chúng có thể bị giới hạn trong phạm vi
số hữu tỷ hoặc
số nguyên. Một số thuật toán có thể đòi hỏi các giới hạn khác đối với trọng số. Chẳng hạn,
thuật toán Dijkstra chỉ dùng được cho các trọng số dương.
Trọng số của đường đi hoặc
trọng số của cây trong một đồ thị có trọng số là tổng trọng số của các cạnh được chọn. Đôi khi một cạnh không tồn tại được gán một trọng số đặc biệt để biểu diễn giá trị vô cùng. Từ
chi phí đôi khi được dùng để chỉ trọng số.
